package com.wuda.util;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * <p>
 * 字符树,具有相同前缀的字符串在同一个子树中.将字符串(单词)拆分成单个char,每个char组成一个节点.比如"world"这个字符串,就会被拆分成w,o
 * ,r,l,d五个字符, 其中w是o的父节点, o是r的父节点...,d是这个单词的结尾,即d所在的这个节点的
 * {@link TreeNode#isWordEnd} 为true.当再加入<i>
 * wake</i>这个单词时,那么<i>w</i>就会共有上面<i>world</i>中<i>w</i>的节点,然后<i>a</i>
 * 是<i>o</i>的兄弟节点
 * 
 * </p>
 * 
 * @author wuda
 * 
 */
public class CharacterTree {

	private final TreeNode root = new TreeNode(null, null, null, false); // 根节点

	/**
	 * 主要用于{@link #findChild(TreeNode, Character)}
	 * 方法,缓存给定的节点<i>parent</i>的子元素<i><childElement</i>所在的节点对象.这个缓存对于查找有绝对大的帮助
	 */
	private Map<String, TreeNode> nodesCache = new HashMap<String, CharacterTree.TreeNode>();

	/**
	 * <p>
	 * 构造一棵空树,然后你可以通过{@link #add(String)}方法来添加数据
	 * </p>
	 */
	public CharacterTree() {

	}

	/**
	 * <p>
	 * 加载给定的资源构造一棵树,该资源中每个单词必须占一行;如果有新的数据,你可以通过{@link #add(String)}方法来添加数据
	 * </p>
	 * 
	 * @throws IOException
	 *             读取资源文件时错误
	 */
	public void load(String resource) throws IOException {
		InputStream in = this.getClass().getResourceAsStream(resource);
		BufferedReader reader = new BufferedReader(new InputStreamReader(in));
		String word = null;
		while ((word = reader.readLine()) != null) {
			add(word);
		}
		in.close();
	}

	/**
	 * <p>
	 * 获得根节点
	 * </p>
	 * 
	 * @return {@link TreeNode} root
	 */
	public TreeNode getRoot() {
		return root;
	}

	/**
	 * <p>
	 * 添加一个元素到树中.将字符串拆分成单个char,每个char占一个节点.
	 * </p>
	 * 
	 * @param element
	 *            element
	 * @param score
	 *            得分
	 */
	public void add(String element, float score) {
		if (element == null || element.isEmpty()) {
			return;
		}
		element = element.trim().toLowerCase();
		char[] charArray = element.toCharArray();
		Character c;
		TreeNode current = root;
		int length = charArray.length;
		/**
		 * 将字符串拆分成单个char,每个char占一个节点
		 */
		for (int i = 0; i < length; i++) {
			c = charArray[i];
			if (i != length - 1) {
				current = add(current, c, false);
			} else { // 单词的结尾的char
				current = add(current, c, true, score);
			}
			if (i == 0) {// 第一个字符,即根节点root的子节点
				String key = getCacheKey(root, c);
				if (!nodesCache.containsKey(key)) {
					nodesCache.put(key, current);
				}
			}
		}

	}

	/**
	 * <p>
	 * 添加一个元素到树中.将字符串拆分成单个char,每个char占一个节点.
	 * </p>
	 * 
	 * @param element
	 *            element
	 */
	public void add(String element) {
		add(element, 0.0f);
	}

	/**
	 * <p>
	 * 添加一个元素到树中.将字符串拆分成单个char,每个char占一个节点.
	 * </p>
	 * 
	 * @param word
	 *            {@link Word}
	 */
	public void add(Word word) {
		if (word == null) {
			return;
		}
		add(word.getValue(), word.getScore());
	}

	/**
	 * <p>
	 * 在给定的节点下添加指定的元素
	 * </p>
	 * 
	 * @param node
	 *            {@link TreeNode}
	 * @param element
	 *            element
	 * @param isWordEnd
	 *            当前这个元素是否一个单词的结尾
	 * @param score
	 *            得分
	 * @return 这个元素所在的节点
	 */
	private TreeNode add(final TreeNode node, Character element,
			boolean isWordEnd, float score) {
		TreeNode child_one = node;
		TreeNode child_two = node.firstChild;
		element = Character.toLowerCase(element);
		if (child_two == null) { // 第一个子节点就为空
			child_two = new TreeNode(element, null, null, isWordEnd);
			node.firstChild = child_two;
			return child_two;
		}
		while (true) {
			if (child_two == null) {
				child_two = new TreeNode(element, null, null, isWordEnd);
				child_one.nextSibling = child_two;
				return child_two;
			} else if (child_two.element.equals(element)) {// 要添加的元素已经存在
				/**
				 * 比如之前添加了一个"计算机","算"这个节点肯定不认为是单词的结束,现在的单词是"计算",那么此时element就是"算"
				 * ,这个节点也应该设置为单词的结束点
				 */
				if (child_two.isWordEnd == false) {
					child_two.isWordEnd = isWordEnd;
				}
				return child_two;
			}
			child_one = child_two;
			child_two = child_two.nextSibling;
		}
	}

	/**
	 * <p>
	 * 在给定的节点下添加指定的元素
	 * </p>
	 * 
	 * @param node
	 *            {@link TreeNode}
	 * @param element
	 *            element
	 * @param isWordEnd
	 *            当前这个元素是否一个单词的结尾
	 * @return 这个元素所在的节点
	 */
	private TreeNode add(final TreeNode node, Character element,
			boolean isWordEnd) {
		return add(node, element, isWordEnd, 0.0f);
	}

	/**
	 * <p>
	 * 找出给定的节点<i>parent</i>的子元素<i><childElement</i>所在的节点对象
	 * </p>
	 * 
	 * @param parent
	 *            当前指定的节点
	 * @param childElement
	 *            指定的元素
	 * @return 当前指定元素所在的节点的对象,这个节点必须是<i>parent</i>的子节点,如果没有找到则返回null
	 */
	public TreeNode findChild(TreeNode parent, Character childElement) {
		if (parent == null || childElement == null) {
			return null;
		}

		TreeNode child = parent.firstChild;
		if (child == null) {
			/**
			 * 说明parent这个节点是叶子节点,对于叶子节点不做缓存,理由是：
			 * 
			 * <pre>
			 * 1:从时间上看,如果已经知道是叶子节点,则直接返回比查找缓存更快
			 * 2:叶节点数量比较多,不做缓存也可以节省内存
			 * </pre>
			 */
			return null;
		}
		childElement = Character.toLowerCase(childElement);
		String key = getCacheKey(parent, childElement);
		if (nodesCache.containsKey(key)) {
			return nodesCache.get(key);
		}

		while (child != null && child.element.equals(childElement) == false) {
			child = child.nextSibling;
		}
		nodesCache.put(key, child);
		return child;
	}

	/**
	 * <p>
	 * 查找以前缀<i>prefix</i>开头的所有单词.
	 * </p>
	 * 
	 * @param prefix
	 *            前缀
	 * @param queue
	 *            保存结果
	 */
	public void findPrefix(String prefix, final PriorityLinkedQueue<Word> queue) {
		if (prefix == null || prefix.isEmpty()) {
			return;
		}
		prefix = prefix.trim().toLowerCase();
		char[] charArray = prefix.toCharArray();
		TreeNode last_node = root;// 前缀prefix的最后一个字符所在的节点,比如：前缀是"jav",则last_node就是"v"所在的节点
		for (int i = 0; i < prefix.length(); i++) {
			last_node = findChild(last_node, charArray[i]);
		}
		if (last_node == null) {
			return;
		}
		LinkedList<BackNode> backs = new LinkedList<BackNode>(); // 回溯节点信息
		backs.addLast(new BackNode(last_node.firstChild, prefix.length())); // 初始化
		StringBuilder buffer = new StringBuilder(prefix);
		TreeNode node = null;
		BackNode back = null;
		while (backs.isEmpty() == false) {
			back = backs.removeLast();
			node = back.node;
			buffer.setLength(back.prefixLength); // 查找的字符串也需要回溯
			while (node != null) {
				buffer.append(node.element);
				if (node.isWordEnd()) {
					queue.add(new Word(buffer.toString(), node.score));
				}
				if (node.nextSibling != null) {
					backs.addLast(new BackNode(node.nextSibling, buffer
							.length() - 1)); // 保存回溯节点信息
				}
				node = node.firstChild; // 一直往节点的firstChild遍历,直到firstChild为空则向上回溯
			}
		}
	}

	/**
	 * <p>
	 * 只用于遍历时保存回溯节点的信息
	 * </p>
	 * 
	 * @author wuda
	 * 
	 */
	class BackNode {
		TreeNode node = null;
		int prefixLength = 0;

		BackNode(TreeNode node, int prefixLength) {
			this.node = node;
			this.prefixLength = prefixLength;
		}
	}

	private String getCacheKey(TreeNode node, Character c) {
		return node.hashCode() + c.toString();
	}

	/**
	 * <p>
	 * 节点
	 * </p>
	 * 
	 * @author wuda
	 * 
	 */
	public class TreeNode {
		private Character element;
		private TreeNode firstChild; // 第一个儿子节点
		private TreeNode nextSibling; // 下一个兄弟节点

		private boolean isWordEnd = false; // 此节点和它以上的祖先节点是否能组成一个单词
		private float score = 0.0f; // 如果是一个单词的结尾字符,那么给定(如果有)这个单词的评分

		TreeNode(Character element, TreeNode firstChild, TreeNode nextSibling,
				boolean isWordEnd, float score) {
			this.element = element;
			this.firstChild = firstChild;
			this.nextSibling = nextSibling;
			this.isWordEnd = isWordEnd;
			this.score = score;
		}

		TreeNode(Character element, TreeNode firstChild, TreeNode nextSibling,
				boolean isWordEnd) {
			this(element, firstChild, nextSibling, isWordEnd, 0.0f);
		}

		/**
		 * <p>
		 * 此节点和它以上的祖先节点是否能组成一个单词,也就是当前节点是否一个单词的"结尾"
		 * </p>
		 * 
		 * @return true-是,false-否
		 */
		public boolean isWordEnd() {
			return isWordEnd;
		}

		/**
		 * 获得节点的值
		 * 
		 * @return {@link Character}
		 */
		public Character getElement() {
			return element;
		}

		/**
		 * 如果是一个单词的结尾字符,那么返回这个单词的评分(如果有)
		 * 
		 * @return 单词评分
		 */
		public float getScore() {
			return score;
		}

	}
}
